Fibonacci numbers.md (629B)
1 +++ 2 title = "Fibonacci numbers" 3 +++ 4 5 # Fibonacci numbers 6 7 recursive algorithm is in O(2n) 8 using memoization, you get to O(n) 9 10 | Recursive | DP (memoization) | 11 | --- | --- | 12 | **Algorithm** fib(n):<br>**if** n=1 **or** n=2 **then**<br>**return** 1<br>**else**<br>x := fib(n−1)<br>y := fib(n − 2)<br>**return** x + y | **Algorithm** fib(n):<br>**new** array r[1...n]<br>r[1] := 1<br>r[2] := 1<br>**for** i := 3 **to** n **do**<br>r[i] := r[i −1]+r[i −2]<br>**return** r[n] | 13 14 reuse easier sub-problems. order them in way that allows you to reuse them. 15 core of DP: optimal substructures, overlapping subproblems.